#include "skiplist.h"

skiplist_compare g_compare_skiplist;

// 生成新节点的层数（1~MAX_LEVEL）
int random_level() {
    int level = 1;
    // 50%概率增加层数，直到达到最大层或概率不满足
    // RAND_MAX 是 C/C++ 标准库中定义的一个常量，用于表示函数 rand() 能生成的最大随机整数，是理解和使用 rand() 生成随机数的核心概念之一。
    while (rand() < RAND_MAX * PROBABILITY && level < MAX_LEVEL) {
        level++;
    }
    return level;
}

SkipList *skiplist_init()
{
    SkipList *skiplist = (SkipList *)malloc(sizeof(SkipList));
    if (skiplist == NULL)
    {
        return NULL;
    }
    
    skiplist->max_level = 0;

    SkipListNode *head = (SkipListNode*)malloc(sizeof(SkipListNode));
    if (head == NULL)
    {
        free(skiplist);
        return NULL;
    }
    skiplist->head = head;
    head->key = NULL;
    head->value = NULL;

    skiplist->head->level_next = (SkipListNode**)calloc(MAX_LEVEL,sizeof(SkipListNode*));
    if (skiplist->head->level_next == NULL)
    {
        free(skiplist);
        free(head);
        return NULL;
    }

    for (int i = 0; i < MAX_LEVEL; i++)
    {
        skiplist->head->level_next[i] = NULL;
    }

    srand((unsigned int)time(NULL));

    return skiplist;
}

/**
 * @brief 插入结点
 * @param slist     跳表
 * @param key       键
 * @param value     值
 * @return -1：失败 0：修改 1：插入成功
 */
int skiplist_insert(SkipList *slist, void *key, void *value)
{
    if (slist == NULL || slist->head == NULL|| key == NULL || g_compare_skiplist == NULL)
    {
        return -1;
    }

    // 1. 记录每一层中，待插入位置的前驱节点（用于后续调整指针）
    SkipListNode* front[MAX_LEVEL] = {NULL};
    SkipListNode* tempNode = slist->head;

    // 2. 从最高层向下遍历，找到各层的前驱节点
    for (int i = slist->max_level - 1; i >= 0; i--)
    {
        while (tempNode->level_next[i] != NULL && g_compare_skiplist(tempNode->level_next[i]->key,key) < 0)
        {
            tempNode = tempNode->level_next[i];
        }
        front[i] = tempNode;
    }
    
    // 3. 检查key是否已存在（底层的下一个节点）
    tempNode = tempNode->level_next[0];
    if (tempNode != NULL && g_compare_skiplist(tempNode->key,key) == 0)
    {
        return 0;
    }
    
    // 4. 生成新节点的层数
    int new_level = random_level();

    // 5. 若新节点层数超过当前跳表最大层，更新跳表层数和update数组
    if (new_level > slist->max_level)
    {
        for (int i = slist->max_level; i < new_level; i++)
        {
            front[i] = slist->head;
        }
        slist->max_level = new_level;
    }

    // 6. 创建新节点
    SkipListNode *new_node = (SkipListNode*)malloc(sizeof(SkipListNode));
    if (new_node == NULL)
    {
        return -1;
    }
    new_node->key = key;
    new_node->value = value;
    new_node->level_next = (SkipListNode**)calloc(new_level,sizeof(SkipListNode*));
    if (new_node->level_next == NULL)
    {
        free(new_node);
        return -1;
    }

    // 7. 调整各层的指针（将新节点插入到update[i]和update[i]->forward[i]之间）
    for (int i = 0; i < new_level; i++)
    {
        new_node->level_next[i] = front[i]->level_next[i];
        front[i]->level_next[i] = new_node;
    }

    // 宏观可以简单概括为
    // 1.找到前驱
    // 2.查看是否存在
    // 3.生成新结点层级
    // 4.添加

    return 1;
}

/**
 * @brief 删除结点
 * @param slist     跳表
 * @param key       键
 * @return -1：失败 0：不存在 1：删除成功
 */
int skiplist_delete(SkipList *slist, void *key)
{
    if (slist == NULL || slist->head == NULL|| key == NULL || g_compare_skiplist == NULL)
    {
        return -1;
    }

    // 1. 记录每一层中，待删除节点的前驱节点
    SkipListNode* front[MAX_LEVEL] = {NULL};
    SkipListNode* tempNode = slist->head;

    // 2. 从最高层向下遍历，找到各层的前驱节点
    for (int i = slist->max_level - 1; i >= 0; i--)
    {
        while (tempNode->level_next[i] != NULL && g_compare_skiplist(tempNode->level_next[i]->key,key) < 0)
        {
            tempNode = tempNode->level_next[i];
        }
        front[i] = tempNode;
    }

    // 3. 检查key是否存在（底层的下一个节点）
    tempNode = tempNode->level_next[0];//要删除的点
    if (tempNode != NULL && g_compare_skiplist(tempNode->key,key) != 0)
    {
        return 0;
    }
    else
    {
        // 4. 调整各层的指针（跳过待删除节点）
        for (int i = 0; i < slist->max_level; i++)
        {
            if (front[i]->level_next[i] != tempNode)
            {
                continue;// 该层无此节点，无需继续调整
            }
            front[i]->level_next[i] = tempNode->level_next[i];
        }
        
    }

    // 5. 释放待删除节点的内存
    free(tempNode->level_next);
    free(tempNode);

    // 6. 若最高层无节点，降低跳表的最大层数
    while (slist->max_level > 1 && slist->head->level_next[slist->max_level - 1] == NULL) 
    {
        slist->max_level--;
    }

    // 宏观可以简单概括为
    // 1.找到前驱
    // 2.查看是否存在
    // 3.删除
    // 4.调整层数

    return 1;
}

int skiplist_modify(SkipList* slist,void *key,void *value)
{
    if (slist == NULL || slist->head == NULL|| key == NULL || g_compare_skiplist == NULL)
    {
        return -1;
    }

    // 1. 记录每一层中，待插入位置的前驱节点（用于后续调整指针）
    SkipListNode* front[MAX_LEVEL] = {NULL};
    SkipListNode* tempNode = slist->head;

    // 2. 从最高层向下遍历，找到各层的前驱节点
    for (int i = slist->max_level - 1; i >= 0; i--)
    {
        while (tempNode->level_next[i] != NULL && g_compare_skiplist(tempNode->level_next[i]->key,key) < 0)
        {
            tempNode = tempNode->level_next[i];
        }
        front[i] = tempNode;
    }
    
    // 3. 检查key是否已存在（底层的下一个节点）
    tempNode = tempNode->level_next[0];
    if (tempNode != NULL && g_compare_skiplist(tempNode->key,key) == 0)
    {
        // tempNode->value = value;
        memcpy((char*)tempNode->value,(char*)value,strlen((char*)value) + 1);
        return 0;
    }
    return -1;
}

void* skiplist_search(SkipList* slist, void *key)
{
    if (slist == NULL || slist->head == NULL|| key == NULL || g_compare_skiplist == NULL)
    {
        return NULL;
    }

    // 1. 记录每一层中，待插入位置的前驱节点（用于后续调整指针）
    SkipListNode* front[MAX_LEVEL] = {NULL};
    SkipListNode* tempNode = slist->head;

    // 2. 从最高层向下遍历，找到各层的前驱节点
    for (int i = slist->max_level - 1; i >= 0; i--)
    {
        while (tempNode->level_next[i] != NULL && g_compare_skiplist(tempNode->level_next[i]->key,key) < 0)
        {
            tempNode = tempNode->level_next[i];
        }
        front[i] = tempNode;
    }
    
    // 3. 检查key是否已存在（底层的下一个节点）
    tempNode = tempNode->level_next[0];
    if (tempNode != NULL && g_compare_skiplist(tempNode->key,key) == 0)
    {
        return tempNode->value;
    }
    return NULL;
}